package com.sheng.leetcode.year2022.month06.day24;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/06/24
 *
 * 515. 在每个树行中找最大值
 *
 * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 *
 * 示例1：
 * 输入: root = [1,3,2,5,3,null,9]
 * 输出: [1,3,9]
 *
 * 示例2：
 * 输入: root = [1,2,3]
 * 输出: [1,3]
 *
 * 提示：
 *
 * 二叉树的节点个数的范围是 [0,104]
 * -231 <= Node.val <= 231 - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0515 {

    @Test
    public void test01(){
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(2);
        left.left = new TreeNode(5);
        left.right = new TreeNode(3);
        right.right = new TreeNode(9);
        root.left = left;
        root.right = right;
        List<Integer> list = new Solution().largestValues(root);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}
class Solution {
    List<Integer> integerList = new ArrayList<>();
    public List<Integer> largestValues(TreeNode root) {
        //层序遍历
        List<TreeNode> treeNodeList = new ArrayList<>();
        if (root != null) {
            treeNodeList.add(root);
        }
        if (treeNodeList.size() > 0) {
            bfs(treeNodeList);
        }
        return integerList;
    }

    public void bfs(List<TreeNode> treeNodeList) {
        List<TreeNode> treeNodes = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        for (TreeNode treeNode : treeNodeList) {
            if (treeNode.val > max) {
                max = treeNode.val;
            }
            if (treeNode.left != null) {
                treeNodes.add(treeNode.left);
            }
            if (treeNode.right != null) {
                treeNodes.add(treeNode.right);
            }
        }
        integerList.add(max);
        if (treeNodes.size() > 0) {
            bfs(treeNodes);
        }
    }
}

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
